Skip to main content

​
FNP - Proof Systems - Halo2 Zero-Knowledge Circuits

​
Summary (Explain Like I’m 5)

Imagine you want to prove to a bank that you have $1000 in your account without showing them your bank statement (privacy). Halo2 does this magic using zero-knowledge proofs:
  • You create a “proof” (a mathematical certificate)
  • Bank verifies the proof (without learning anything else)
  • Bank is convinced you have $1000
  • Bank learns nothing about how you got it
In FNP: When you insert a character, you prove: “This character is at the correct position and I’m authorized to edit it” - without revealing the character itself.

​
Technical Deep Dive

Halo2 is a zero-knowledge proof system using Inner Product Arguments (IPA) to achieve compact proofs (~514 bytes) with efficient verification. Three Properties of ZK Proofs (The “Triangle”):
  1. Completeness: Honest prover always generates valid proofs 
    If statement TRUE → Prover generates accepting proof
  2. Soundness: Dishonest prover can’t forge false proofs 
    If statement FALSE → Prover (with <50% probability) generates rejecting proof
  3. Zero-Knowledge: Proof reveals nothing about witness 
    Verifier learns: "Statement is TRUE"
Verifier learns: NOTHING about how/why
Arithmetic Constraint System: All constraints are polynomial equations over finite field F_p (p = BLS12-381 prime ≈ 2^255): 
Constraint at column j (row i):
  Q(i, j) = 0  for all rows j

Example (comparing three positions):
  LEFT < MIDDLE < RIGHT

Polynomial: Q = (middle - left)·(right - middle) - 1 = 0
  Satisfiable only when: left < middle < right
FNP Circuit Specifications:
CircuitPurposeConstraintsProof Size
RangeCheckChipProve 0 ≤ x < 2^256~300~400 bytes
ComparisonChipProve a < b~2,800~420 bytes
M2OREChipVerify order-reveal~2,250~450 bytes
KyberChipVerify key encapsulation~3,000~480 bytes
InsertProofCircuitFull insert verification~51,350~514 bytes
DeleteProofCircuitFull delete verification~51,900~528 bytes
Inner Product Argument (IPA): 
Goal: Prove commitment C is to polynomial p(x) where p(ζ) = v

Proof Structure:
  - Commitment C (group element)
  - Opening values (commitments at ζ)
  - IPA proof (log n group elements)

For circuit with n ≈ 65,536 constraints:
  Proof size: log₂(65536) ≈ 16-17 group elements
  Compressed: ≈ 514-528 bytes

Verification Time: O(log n) ≈ <15ms on mobile
Prover Time: O(n) ≈ 1.2ms with optimization

​
Mermaid Diagrams

​
Key Terms

  • ZK Proof → Mathematical certificate proving statement truth without revealing witness
  • Arithmetic Circuit → Constraints as polynomial equations over finite field
  • IPA → Inner Product Argument; compact proof with O(log n) size and verification
  • Commitment → Cryptographic binding to value; can’t change commitment without breaking security
  • Witness → Secret data used to generate proof; must remain hidden
  • Public Input → Known data; verifier already knows this
  • Constraint System → Set of polynomial equations that must evaluate to zero
  • Field Arithmetic → All operations mod p (BLS12-381 prime ≈ 2^255)

​
Q/A

Q: How does the prover prove something without revealing the witness? A: Prover commits to witness (using hash/Merkle tree), then opens specific points without revealing the full witness. Verifier checks that polynomial satisfies constraints at those points. Similar to proving “I know the answer to a puzzle” by solving only a few challenges without revealing full solution. Q: Why is proof size only 514 bytes for 51,350 constraints? A: IPA achieves O(log n) proof size through recursive folding. Instead of sending all 51,350 constraint openings, prover sends only ~16-17 group elements that collectively prove the entire circuit. Verifier reconstructs full constraint check from compact proof. Q: Can verifier cheat and accept false proofs? A: Soundness guarantees: if statement is false, dishonest prover needs to break a hard problem (discrete log, pairing security). Probability of forging accepting proof < 50% per attempt. Multiple proofs exponentially decreases forgery probability. Q: Does verifier need to know prover’s secrets to verify? A: No. Verifier has public input and proof. Verifier checks: (1) Polynomial constraints satisfied at point ζ, (2) Commitment opens to stated value, (3) IPA proof is valid. All done without access to witness or secret keys. Q: What happens if someone replays an old proof? A: Proofs are non-transferable if public input includes timestamp/nonce. FNP includes operation ID (hash of timestamp + position + content) in circuit witness. Same operation can’t be replayed: changing timestamp changes circuit input, invalidating old proof. Q: Why <15ms verification time on mobile? A: IPA verifier is O(log n) ≈ 16 pairings. Modern mobile CPU: ~1ms per pairing. 16 pairings × 1ms ≈ 16ms (within budget). Server-side verification with GPU: <1ms. Halo2 proof verification scales logarithmically with circuit size.

​
Example / Analogy

Math Exam Analogy: Without ZK Proof:
  • Teacher: “Prove you know calculus”
  • Student: Shows full exam work (everyone learns solution)
  • Problem: Cheaters copy the work
With ZK Proof:
  • Teacher: “Prove you know calculus”
  • Student: Generates cryptographic proof (no solution shown)
  • Teacher verifies proof mathematically
  • Teacher is convinced student knows calculus
  • Cheaters can’t replicate proof without knowledge
Real-world FNP Example: Alice inserts character “X” into collaborative document: 
Witness (Secret):
  - Alice's M²-ORE secret key
  - Position identifier [500, 0, 1]
  - Content "X"
  - Kyber randomness for encryption

Public Input:
  - M²-ORE public key (known to all)
  - Kyber public key (known to all)
  - Encrypted position (M²-ORE ciphertext)
  - Encrypted content (Kyber ciphertext)
  - Operation ID timestamp

Halo2 Circuit Verifies (without decryption):
  ✓ Encrypted position encrypts legal identifier
  ✓ Encrypted content encrypts valid character
  ✓ Alice is authorized (her signature verifies)
  ✓ Operation is causally consistent (Lamport clock valid)

Server: Accepts proof and merges operation
Other Clients: Verify proof (no secrets accessed)
Cross-References: System Overview, FNP Protocol Flow, M²-ORE Encryption, Kyber-1024 Category: Proof Systems | Cryptography | Zero-Knowledge | Security Difficulty: Advanced ⭐⭐⭐⭐⭐ Updated: 2025-11-28